package com.mystudy.leetcode.problem.tree.p_235;

import com.mystudy.leetcode.base.TreeNode;

/**
 * @program: infoalgorithm
 * @description: 二叉搜索树的最近公共祖先
 * @author: zhouzhilong
 * @create: 2019-07-26 09:00
 **/
public class Solution {
    /**
     * 对于一个父亲节点来说，如何确认这个节点是否是两个节点的最小父亲节点．
     * 首先，如果父亲节点不是其中的一个节点，那么必然的两个节点分别在两棵树之中．如果分布在同一棵树，那么
     * 必然还有更小的父亲节点．
     * 如果父亲节点是其中的一个节点，那么这两个节点也符合节点值不大于或者不小于父亲节点的值．
     *
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(p.val>root.val && q.val>root.val){
            return lowestCommonAncestor(root.right,p,q);
        }else if(p.val< root.val && q.val <root.val){
            return lowestCommonAncestor(root.left,p,q);
        }else{
            return root;
        }
    }
}
